﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OI_VS_CSharp {
    public class Solution {
        public int[] NextGreaterElement(int[] nums1, int[] nums2) {
            Dictionary<int, int> result = new Dictionary<int, int>();
            Stack<int> stack = new Stack<int>();
            for (int i = nums2.Length - 1; i >= 0; i--) {
                int c = nums2[i];
                while (stack.Count > 0 && stack.Peek() < c) {
                    stack.Pop();
                }
                int nextMax = stack.Count > 0 ? stack.Peek() : -1;
                result.Add(c, nextMax);
                stack.Push(c);
            }
            List<int> ret = new List<int>();
            foreach (int c in nums1) {
                if (result.ContainsKey(c)) {
                    ret.Add(result[c]);
                } else {
                    ret.Add(-1);
                }
            }
            return ret.ToArray();
        }
    }

    public class Program {
        static readonly Solution solution = new Solution();
        static void Main() {
            var ans = solution.NextGreaterElement(new int[] { 4, 1, 2 }, new int[] { 1, 3, 4, 2 });
            foreach (int x in ans) {
                Console.Write(x);
                Console.Write(' ');
            }
        }
    }
}